'''
https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/description/?envType=study-plan-v2&envId=graph-theory
'''
from collections import deque
from typing import List


class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        m, n = len(maze), len(maze[0])
        q = deque([entrance])
        visited = [[False] * n for _ in range(m)]
        step = 0
        while q:
            for _ in range(len(q)):
                x, y = q.popleft()
                if visited[x][y]:
                    continue
                visited[x][y] = True
                for tx, ty in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                    if tx < 0 or ty < 0 or tx >= m or ty >= n:
                        if [x, y] != entrance:
                            return step
                        continue
                    if maze[tx][ty] == '.':
                        q.append([tx, ty])
            step += 1
        return -1